import java.util.Arrays;

/**
 * 插值查找算法：二分法查找算法的升级版，会根据当前插入值在整个数组中的比例，来自适应找到合适的几分法；
 *      注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。
 *      反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择（也许不如二分法快）
 */
public class InsertSearch {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for(int i = 1; i <= 100;i++){
            arr[i-1] = i;
        }
//        System.out.println(Arrays.toString(arr));

        //调用插值查找算法
        int i = insertSearch(arr, 78, 0, arr.length - 1);
        System.out.println("查找值的索引为："+i);
    }

    /**
     * 差值查找算法的前提要求也是数组要有序
     * @param arr  传入的数组
     * @param value  要查找的值
     * @param low  左边的索引
     * @param high  右边的索引
     * @return
     */
    public static int insertSearch(int[] arr, int value,int low,int high) {
        //对输入的索引，以及查找值，进行鉴定，确保查找值在数组里面存在
        if (low > high || value > arr[arr.length - 1] || value < arr[0]) {
            return -1;
        }
        //创建数组的头索引
        int head = low;
        //创建数组的尾索引
        int end = high;
        //创建中间值索引（并不一定是最中间的索引）
        int mid = head + (value - arr[head]) / (arr[end] - arr[head]) * (end - head);
        //获得中间索引的值
        int midVal = arr[mid];
        //根据判断
        if (value > midVal) {//向右递归查找
            return insertSearch(arr,value,mid+1,high);
        }else if (value < midVal) {//向左递归查找
            return insertSearch(arr,value,low,mid-1);
        }else {
            return mid;
        }
    }
}
